﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    class Problem73 : IProblem
    {
        public string Calculate()
        {
            //nadjemo najblizi gornjoj granici, i smanjujemo (preskacuci one koji imaju gcd koji nije 1)
            //za svakog takvog je count++
            //kad padne ispod limita, ide dalje

            double lower = 1/3.0;
            double upper = 0.5;

            int count = 0;

            int limit = 12000;

            for (int d = 4; d <= limit; d++)
            {
                int numerator = (int)(upper * d);

                double fraction = numerator / (double)d;

                while (fraction > lower)
                {
                    while (CommonFunctions.GreatestCommonDivisor(d, numerator) != 1)
                    {
                        numerator--;
                    }

                    fraction = numerator / (double)d;

                    if (fraction <= lower)
                        break;

                    count++;
                    numerator--;

                    fraction = numerator / (double)d;
                }
            }


            return count.ToString();
        }
    }
}
